package summary;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @Author: 海琳琦
 * @Date: 2022/3/13 15:13
 * https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 */
public class Title112 {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }

        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        Stack<TreeNode> stack = new Stack<>();
        if (root == null) {
            return false;
        }
        Stack<Integer> pathSum = new Stack<>();
        stack.push(root);
        pathSum.push(root.val);
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            Integer path = pathSum.pop();
            if (pop.left == null && pop.right == null && path == targetSum) {
                return true;
            }
            if (pop.right != null) {
                stack.push(pop.right);
                pathSum.push(path + pop.right.val);
            }
            if (pop.left != null) {
                stack.push(pop.left);
                pathSum.push(path + pop.left.val);
            }
        }
        return false;
    }


    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        LinkedList<TreeNode> list = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();
        list.offer(root);
        path.offer(root.val);
        while (!list.isEmpty()) {
            int size = list.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = list.poll();
                Integer value = path.poll();
                if (poll.left == null && poll.right == null && value == targetSum) {
                    return true;
                }
                if (poll.left != null) {
                    list.offer(poll.left);
                    path.offer(value + poll.left.val);
                }
                if (poll.right != null) {
                    list.offer(poll.right);
                    path.offer(value + poll.right.val);
                }
            }
        }
        return false;
    }


    public static boolean hasPathSum3(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return dfs(root, targetSum);
    }

    private static boolean dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            return true;
        }
        return dfs(root.left, targetSum) || dfs(root.right, targetSum);
    }

    public static void main(String[] args) {

    }
}
